UVa/10397 - Connect the campus/10397.cpp

   1 /*
   2   Problem 10397 - Connect the campus
   3
   4 Hallar un árbol de recubrimiento mínimo (Algoritmo de Prim)
   5
   6 Autor: Andrés Mejía P.
   7 Fecha: Marzo 25/2008
   8  */
   9 #include <set>
  10 #include <iostream>
  11 #include <vector>
  12 #include <queue>
  13 #include <cmath>
  14
  15 using namespace std;
  16
  17 typedef pair<int, int> point;
  18 typedef pair<double, int> edge; //Edge incidente en second con longitud first
  19 typedef vector<int> * graph;
  20
  21
  22 double euclidean(const point &a, const point &b){ return hypot(a.first-b.first, a.second-b.second); }
  23
  24 int main(){
  25   int n;
  26   while (cin >> n){
  27     vector<point>  p(n+1); //p[i] contiene las coordenadas del punto etiquetado con i
  28     graph g = new vector<int>[n+1]; //g[i] contiene el set de vecinos "gratuitos" del nodo i (ya existentes en el grafo)
  29     vector<bool> visited(n+1, false);
  30     for (int i=0; i<n; ++i){
  31       int x,y;
  32       scanf("%d%d", &x, &y);
  33       p[i] = make_pair(x, y);
  34     }
  35
  36     priority_queue<edge, vector<edge>, greater<edge> > q;
  37
  38     int m;
  39     cin >> m;
  40     for (int i=0; i<m; ++i){
  41       int x, y;
  42       scanf("%d%d", &x, &y);
  43       g[x-1].push_back(y-1);
  44       g[y-1].push_back(x-1);
  45     }
  46
  47     q.push( edge(0.0, 0) ); //empiezo arbitrariamente en el primer nodo
  48
  49
  50     double totalDistance = 0.0;
  51
  52     while (!q.empty()){
  53       edge nearest = q.top(); q.pop();
  54
  55       int actualNode = nearest.second;
  56
  57       if (!visited[actualNode]){
  58         //cout << "Visitando " << actualNode << " (" << p[actualNode].first << ", " << p[actualNode].second << ")" << " en " << nearest.first << endl;
  59         visited[actualNode] = true;
  60         totalDistance += nearest.first;
  61         vector<int> neighbors = g[actualNode];
  62         for (int i = 0; i < neighbors.size(); ++i){
  63           if (!visited[neighbors[i]]){
  64             q.push( edge(0.0, neighbors[i]) );
  65           }
  66         }
  67
  68         for (int i = 0; i < n; ++i){
  69           if (!visited[i]){
  70             q.push( edge(euclidean(p[actualNode], p[i]), i) );
  71           }
  72         }
  73       }
  74     }
  75     printf("%.2f\n", totalDistance);
  76     delete [] g;
  77   }
  78   return 0;
  79 }